package 贪心;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 跳跃游戏.java
 * @Description TODO
 * @createTime 2020年10月19日 14:54:00
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 判断你是否能够到达最后一个位置。
 *
 * 示例 1:
 *
 * 输入: [2,3,1,1,4]
 * 输出: true
 * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
 *
 * 总结：很经典的贪心问题 用一个变量变量记录能到达的最远距离
 *      然后从第一个元素开始遍历 只有当这个元素小于 能到达的最远距离 就记录这个元素能到达的最远距离 不断更新这个距离
 *      通过局部最优解 得到总体最优解 每个元素能到达的最远距离就是局部最优解
 *
 *      贪心算法，每个位置都计算自己能达到的最远距离，同时每个位置要判断自己是否可达，
 *      也就是本位置需要在当前最远能到达的距离中。最终计算出来能到达的最远距离，与数组长度比较即可。
 */
public class 跳跃游戏 {
//    class Solution {
//        public boolean canJump(int[] nums) {
//            int map=0;
//            for(int i=0;i<nums.length;i++){
//                if(i<=map){
//                    map=Math.max(map,i+nums[i]);
//
//                }
//
//                if(map>=nums.length-1){
//                    return true;
//                }
//
//            }
//
//            return false;
//        }
//    }

}
